import java.util.*;

/**
 * 239. 滑动窗口最大值
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class Solutions_239 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        int k = 3;  // output: {3, 3, 5, 5, 6, 7}
//        int k = 2;  // output: {3, 3, -1, 5, 5, 6，7}
        int k = 1;  // output: {1, 3, -1, -3, 5, 3, 6, 7}

        int[] result = maxSlidingWindow(nums, k);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 解题思路：单调队列
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null) {
            return null;
        }
        int len = nums.length;
        // 结果数组：res[i] 为 (i - k, i] 区间中的最大值
        int[] res = new int[len - k + 1];
        int index = 0;
        // 双端队列
        Deque<Integer> queue = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                // 对于之前添加的，数值小于 nums[i] 的，全部出队
                // 关键：当一个元素进入队列时，队列之前的所有比它小的元素就不会再对答案产生影响，故进行弹出
                queue.pollLast();
            }
            // 添加到队尾
            queue.addLast(i);
            // 窗口中已经有元素 k 个，需要记录最大值
            if (i >= k - 1) {
                while (i - queue.peek() >= k) {
                    // 关键：最大值所在索引不能与 i 之前的距离大于 k
                    queue.poll();
                }
                // 队首元素一定是窗口中的最大值所在索引
                res[index++] = nums[queue.peek()];
            }
        }
        return res;
    }
}
